The proliferation of network computing has shaped how society transacts business and engages in personal communication. As reliance on computer networks grows, the flow of information between computers continues to increase in dramatic fashion. Accompanying this increased flow of information is a proportionate concern for network security. Commercial users, who regularly conduct business involving the exchange of confidential or company proprietary information over their computer networks, demand that such information is secure against interception by an unauthorized party or corruption. In addition, with the acceptance of such applications as electronic commerce over the global Internet, all users recognize the critical role cryptographic systems play in maintaining the integrity of network communication.
The goal of cryptography is to keep messages secure. A message can be defined as information or data that is arranged or formatted in a particular way. In general, a message, sometimes referred to as “plaintext” or “cleartext”, is encrypted or transformed using a cipher to create “ciphertext,” which disguises the message in such a way as to hide its substance. In the context of cryptography, a cipher is a mathematical function that can be computed by a data processor. Once received by the intended recipient, the ciphertext is decrypted to convert the ciphertext back into plaintext. Ideally, ciphertext sufficiently disguises a message in such a way that even if the ciphertext is obtained by an unintended recipient, the substance of the message cannot be discerned from the ciphertext.
Many different encryption/decryption approaches for protecting information exist. The selection of an encryption/decryption scheme generally depends upon considerations such as the types of communications to be made more secure, the particular parameters of the network environment in which the security is to be implemented, and the desired level of security. Since the level of security often has a direct effect on system resources, an important consideration is the particular system on which a security scheme is to be implemented.
For example, for small applications that require a relatively low level of security, a traditional restricted algorithm approach may be appropriate. With a restricted algorithm approach, a group of participants agree to use a specific, predetermined algorithm to encrypt and decrypt messages exchanged among the participants. Because the algorithm is maintained in secret, a relatively simple algorithm may be used. However, if secrecy of the algorithm is compromised, the algorithm must be changed to preserve secure communication among the participants. Scalability, under this approach, is problematic; that is, as the number of participants increases, keeping the algorithm secret and updating it when compromises occur place an undue strain on network resources. In addition, standard algorithms cannot be used because each group of participants must have their own unique algorithm.
To address the shortcomings of traditional restricted algorithm approaches, many contemporary cryptography approaches use a key-based algorithm. Basically, two types of key-based algorithms exist: (1) symmetric and (2) asymmetric, such as public key. As a practical matter, a key forms one of the inputs to a mathematical function that a computer or processor uses to generate a ciphertext.
Public key algorithms are designed so that the key used for encryption is different than the key used for decryption. The decryption key cannot be determined from the encryption key, at least not in any reasonable amount of time using reasonable computing resources. Typically, the encryption key (public key) is made public so that anyone, including an eavesdropper, can use the public key to encrypt a message. However, only a specific participant in possession of the decryption key (private key) can decrypt the message.
Public key algorithms, however, are not often employed as a mechanism to encrypt messages largely because such algorithms consume an inordinate amount of system resources and time to encrypt entire messages. Further, public key encryption systems are vulnerable to chosen-plaintext attacks, particularly when there are relatively few possible encrypted messages.
As a result, a public key cryptosystem is utilized to establish a secure data communication channel through key exchanges among the participants. That is, two or more parties, who wish to communicate over a secure channel, exchange or make available to each other public (or non-secure) key values. Each party uses the other party's public key value to privately and securely compute a private key, using an agreed-upon algorithm. The parties then use their derived private keys in a separate encryption algorithm to encrypt messages passed over the data communication channel. Conventionally, these private keys are valid only on a per communication session basis, and thus, are referred to as session keys. These session keys serve to encrypt/decrypt a specified number of messages or for a specified period of time. For instance, in a typical scenario, two users or participants A and B seek to communicate over a secure channel in which user A wants to send a message to B. Thus, user A is considered a publisher of a message to user B, who is acting as a subscriber. The public key algorithm establishes a secure channel between publisher, A, and subscriber, B, as follows:
1. B provides a public key, B, to A.
2. A generates a random session key SK, encrypts it using public key B and sends it to B.
3. B decrypts the message using private key, b (to recover the session key SK).
4. Both A and B use the session key SK to encrypt their communications with each other, each user discards the session key after completing the communication.
The above approach provides the added security of destroying the session key at the end of a session, thereby providing greater protection against unauthorized access by eavesdroppers.
A known public key exchange method is the Diffie-Hellman algorithm described in U.S. Pat. No. 4,200,770. The Diffie-Hellman method relies on the difficulty associated with calculating discrete logarithms in a finite field. According to this method, two participants, A and B, each select random large numbers a and b, which are kept secret. A and B also agree (publicly) upon a base number p and a large prime number q, such that p is primitive mod q. A and B exchange the values of p and q over a non-secure channel or publish them in a database that both can access. Then A and B each privately compute public keys A and B, respectively, as follows:A privately computes a public key A as: A=pa mod (q)  (1)B privately computes a public key B as: B=pb mod (q)  (2)
A and B then exchange or publish their respective public keys A and B and determine private keys ka and kb as follows:A computes a private key ka as: ka=Ba mod (q)  (3)B computes a private key kb as: kb=Ab mod (q)  (4)
As evident from equation (3), A's private key is a function of its own private random number, a, and the public key, B. Likewise, equation (4) indicates that B's private key depends on its own private number, b, and the public key of A. As a result, A and B arrive at the shared secret key. Substituting for A and B of equations (3) and (4) using equations (1) and (2), respectively yields:ka=(pb mod (q))a mod (q) and kb=(pa mod (q))b mod (q)ka=pba mod (q) and kb=pab mod (q)Therefore, ka=kb.
Using the Diffie-Hellman protocol, A and B each possesses the same secure key ka, kb, which can then be used to encrypt messages to each other. An eavesdropper who intercepts an encrypted message can recover it only by knowing the private values, a or b, or by solving an extremely difficult discrete logarithm to yield a or b. Thus, the Diffie-Hellman protocol provides a secure approach for the exchange of keys.
FIG. 1 is a flow diagram that shows a way to use the Diffie-Hellman protocol in a broadcast context involving three users Alice, Bob, and Carol. The approach is applicable to any number of users, however, three users are shown for clarity and simplicity. Initially, as illustrated in block 100, each of the participants Alice, Bob, and Carol randomly generates private integers, a, b, and c, respectively. At block 102, a prime number “q” and integer “p” are agreed upon by the users. These values serve as seed values for later computations.
Thereafter, as illustrated in blocks 104-108 (not necessarily in this order), Alice computes and forwards her public key to Bob, Bob computes and forwards his public key to Carol and Carol computes and forwards her public key to Alice, as follows:X=pa mod (q)  (5)Y=pb mod (q)  (6) Z=pc mod (q)  (7)
In blocks 110-114 (again, not necessarily in this order), user Alice computes Z′, which equals Za mod (q), and sends it to Bob. Bob computes X′, which equals Xb mod (q), and sends it to Carol. Carol computes Y′, which equals Yc mod (q), and sends it to, Alice.
As illustrated in block 116, all the users arrive at a shared secret key, k, by computing the following:Alice computes k: k=Y′a mod (q)=pabc mod (q)  (8)Bob computes k: k=Z′b mod (q)=pabc mod (q)  (9)Carol computes k: k=X′c mod (q)=pabc mod (q)  (10)
After these series of exchanges, all the three involved parties end up with the same secret key (k). An intruder who is monitoring these exchanges would not be able to compute the same key as all the involved parties. The security of Diffie-Hellman key agreement relies on the difficulty of computing discrete logarithms.
However, although the Diffie-Hellman key-exchange algorithm may be used to establish a secure channel in a network environment comprising multiple nodes, the algorithm requires at least N×(N−1) rounds of point-to-point unicast messages between the member nodes. With three nodes, as in this instance, a total of six (6) messages are exchanged as each member node communicates its public key to the other members of the group. For larger broadcast or multicast groups, this method of key-exchange requires extensive message traffic and may introduce appreciable networking delay. For example, with six nodes, the standard broadcast Diffie-Hellman approach requires that a total of thirty (30) messages be exchanged between the members of the group.
Furthermore, when the algorithm is applied to a dynamically changing group of node members, such that members are routinely joining and leaving the group, the entire series of steps need to be repeated every time a new member is added to the group. Thus, whenever a new member is allowed to join an existing group, the standard Diffie-Hellman broadcast approach again requires N×(N−1) rounds of point-to-point unicast messages to sent between the node members. For example, using the standard broadcast Diffie-Hellman approach, to establish a secure channel in a network environment comprising six nodes, a total of thirty (30) messages must be exchanged between the members of the group. In addition, if a seventh node requests entry into the group, the algorithm requires that an additional forty-two (42) messages be exchanged to allow the seventh node to join the existing group. Thus, the algorithm as currently known simply requires too many key exchanges and is not scalable.
One approach for reducing the number of messages that are required to establish a secure channel in a network environment comprising multiple node members is described in co-pending U.S. Patent Application “Operational Optimization of a Shared Secret Diffie-Hellman Key Exchange Among Broadcast or Multicast Groups,” Ser. No. 09/393,410, filed Sep. 10, 1999, by Srivastava.
Based upon the foregoing, there is a clear need for an improved method for exchanging key information that will minimize network processing delays, especially among broadcast or multicast groups whose members dynamically change over time.
There is also an acute need for an improved approach that will enhance the scalability of establishing a secure communication channel for dynamically changing broadcast or multicast groups.
There is further a need for providing a secure communication link that provides a high level of security while requiring relatively fewer system resources and less time to the secure communication link.